#include<bits/stdc++.h>
using namespace std;

struct node {
	int nxt, len, time;
	node(int n = 0, int l = 0, int t = 0) : nxt(n), len(l), time(t) { };
};

const int MAX = 1000009;
typedef pair<int, int> pii;
int n, m, src, dst;
vector<vector<node>> graph;
vector<int> ansd, anst, ans1, ans2;
priority_queue<pii, vector<pii>, greater<pii>> pq;

int djikstra_d(int src, int dst, vector<int>& ans) {
	vector<int> dis(n, MAX), dit(n, MAX), visit(n);
	ans.resize(n);
	dis[src] = 0;
	dit[src] = 0;
	pq.push(pii(0, src));
	while (!pq.empty()) {
		int now = pq.top().second;
		pq.pop();
		if (!visit[now]) {
			visit[now] = 1;
			for (const node& nxd : graph[now]) {
				int nxt = nxd.nxt, len = nxd.len, time = nxd.time;
				if (!visit[nxt]) {
					if (dis[now] + len < dis[nxt]) {
						dis[nxt] = dis[now] + len;
						dit[nxt] = dit[now] + time;
						ans[nxt] = now;
					}
					else if (dis[now] + len == dis[nxt] && dit[now] + time < dit[nxt]) {
						dit[nxt] = dit[now] + time;
						ans[nxt] = now;
					}
					pq.push(pii(dis[nxt], nxt));
				}
			}
		}
	}
	return dis[dst];
}

int djikstra_t(int src, int dst, vector<int>& ans) {
	vector<int> dicnt(n, MAX), dit(n, MAX), visit(n);
	ans.resize(n);
	dicnt[src] = 0;
	dit[src] = 0;
	pq.push(pii(0, src));
	while (!pq.empty()) {
		int now = pq.top().second;
		pq.pop();
		if (!visit[now]) {
			visit[now] = 1;
			for (const node& nxd : graph[now]) {
				int nxt = nxd.nxt, time = nxd.time;
				if (!visit[nxt]) {
					if (dit[now] + time < dit[nxt]) {
						dit[nxt] = dit[now] + time;
						dicnt[nxt] = dicnt[now] + 1;
						ans[nxt] = now;
					}
					else if (dit[now] + time == dit[nxt] && dicnt[now] + 1 < dicnt[nxt]) {
						dicnt[nxt] = dicnt[now] + 1;
						ans[nxt] = now;
					}
					pq.push(pii(dit[nxt], nxt));
				}
			}
		}
	}
	return dit[dst];
}

void dfs(int d, int s, vector<int>& ans, vector<int>& _ans) {
	if (d == s) {
		_ans.push_back(d);
		return;
	}
	dfs(ans[d], s, ans, _ans);
	_ans.push_back(d);
}

int main() {
	scanf("%d %d", &n, &m);
	graph.resize(n);
	for (int i = 0; i < m; ++i) {
		int v1, v2, onw, len, time;
		scanf("%d %d %d %d %d", &v1, &v2, &onw, &len, &time);
		graph[v1].push_back(node(v2, len, time));
		if (!onw) {
			graph[v2].push_back(node(v1, len, time));
		}
	}

	scanf("%d %d", &src, &dst);

	int distance = djikstra_d(src, dst, ansd);
	int totaltime = djikstra_t(src, dst, anst);

	dfs(dst, src, ansd, ans1);
	dfs(dst, src, anst, ans2);

	int issame = 1;
	if (ans1.size() == ans2.size()) {
		for (int i = 0; i < ans1.size(); ++i) {
			if (ans1[i] != ans2[i]) {
				issame = 0;
				break;
			}
		}
	}
	else
		issame = 0;

	printf("Distance = %d", distance);
	if (issame) {
		printf("; ");
	}
	else {
		printf(":");
		for (int i = 0; i < ans1.size(); ++i) {
			if (i)
				printf(" ->");
			printf(" %d", ans1[i]);
		}
		printf("\n");
	}

	printf("Time = %d:", totaltime);
	for (int i = 0; i < ans2.size(); ++i) {
		if (i)
			printf(" ->");
		printf(" %d", ans2[i]);
	}
	printf("\n");
	return 0;
}